/**
 * 选择排序
 */
public class SelectionSort {

    // public void sort(int[] nums) {
    //     int n = nums.length;
    //     // sortedIndex是个分界线，小于sortedIndex的元素已经排序完成，大于sortedIndex的元素还未排序
    //     // 初始化为0，表示整个数组都是未排序的
    //     int sortedIndex = 0;
    //     while (sortedIndex < n) {
    //         // 找到未排序部分[sortedIndex, n)中的最小值，并交换到sortedIndex位置
    //         int minIndex = sortedIndex;
    //         for (int i = sortedIndex + 1; i < n; i++) {
    //             if (nums[i] < nums[sortedIndex]) {
    //                 minIndex = i;
    //             }
    //         }
    //
    //         // 交换最小值和sortedIndex位置的元素
    //         int temp = nums[sortedIndex];
    //         nums[sortedIndex] = nums[minIndex];
    //         nums[minIndex] = temp;
    //         sortedIndex++;
    //     }
    // }

    // 对选择排序进行第一波优化，获得了稳定性
    public void sort(int[] nums) {
        int n = nums.length;
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 在未排序区间找到最小值，nums[minIndex]
            int minIndex = sortedIndex;
            for (int i = sortedIndex + 1; i < n; i++) {
                if (nums[i] < nums[minIndex]) {
                    minIndex = i;
                }
            }
            // 交换最小值和sortedIndex位置的元素
            // 优化：将nums[minIndex]插入到sortedIndex位置
            // 将nums[sortedIndex...minIndex]元素整体后移一位
            int minVal = nums[minIndex];
            // 数组搬移数据
            for (int i = minIndex; i > sortedIndex; i--) {
                nums[i] = nums[i - 1];
            }
            nums[sortedIndex] = minVal;
        }
    }
}
